package leetcode;

/*
112. 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
*/

import java.util.Stack;

public class problems_112 {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(5);
        TreeNode node21 = new TreeNode(4);
        TreeNode node22 = new TreeNode(8);
        TreeNode node31 = new TreeNode(11);
        TreeNode node32 = new TreeNode(13);
        TreeNode node33 = new TreeNode(4);
        TreeNode node41 = new TreeNode(7);
        TreeNode node42 = new TreeNode(2);
        TreeNode node43 = new TreeNode(1);
        node1.left = node21;
        node1.right = node22;
        node21.left = node31;
        node31.left = node41;
        node31.right = node42;
        node22.left = node32;
        node22.right = node33;
        node33.right = node43;
        System.out.println(new Solution().hasPathSum(node1, 22));
    }

    static public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
    static class Solution {
        public boolean hasPathSum(TreeNode root, int sum) {
            if(null==root)return false;
            if(null==root.left && null==root.right) return sum == root.val;
            return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);
        }
    }

//    static class Solution {
//        public boolean hasPathSum(TreeNode root, int sum) {
//            if (null == root) return false;
//            if (root.val == sum) return false;
//            Stack<Integer> stack = new Stack<>();
//            return dfs(root, sum, stack);
//        }
//
//        private boolean dfs(TreeNode node, int target, Stack<Integer> stack) {
//            if (null == node) return false;
//            stack.push(node.val);
//            if (null != node.left && dfs(node.left, target, stack)) return true;
//            if (null != node.right && dfs(node.right, target, stack)) return true;
//            if (null == node.left && null == node.right && target == stack.stream().mapToInt(Integer::intValue).sum()) return true;
//            return false;
//        }
//    }
}